package com.cat.chapter051;

/**
 * @author cat
 * @description https://leetcode.cn/problems/maximum-running-time-of-n-computers/description/
 * @create 2025/7/22 15:21
 * @since JDK17
 */

public class Solution05 {
    public boolean check(int[] batteries, int n, long target) {
        int sum = 0;
        for (int battery : batteries) {
            if (battery >= target) {    //
                n--;
            } else {
                sum += battery;
            }

            if (sum >= n * target) {
                return true;
            }
        }
        return false;
    }

    public long maxRunTime(int n, int[] batteries) {
        int sum = 0, max = 0;
        for (int battery : batteries) {
            sum += battery;
            max = Math.max(max, battery);
        }
        if (sum >= max * n) {   // 可以将它们都当作碎片化的电池
            return sum / n;
        }
        long l = 0, r = max, mid;
        while (l + 1 < r) {
            mid = l + (r - l) / 2;
            if (check(batteries, n, mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
}
